package 其他.华为;

import java.util.*;

/*
    可以不用并查集，直接存map，单线递归深搜(map可以随机访问)

*/
class ConnectFind {
    Map<String,String> P = new HashMap<>();
    //【准备】
    public ConnectFind(String[] ss){

        for (int i = 0; i < ss.length; i++) {
            P.put(ss[i],ss[i]);
        }
    }
    public String find_returnRot(String s){
        while(!P.get(s).equals(s)){
            s=P.get(s);
        }
        return s;
    }
    public void connect(String a,String b){
        String aR = find_returnRot(a);
        String bR = find_returnRot(b);
        if(aR.equals(bR)){
            return;
        }
        P.put(aR,bR);
    }

    public boolean judgeCon(String a, String b){
        return find_returnRot(a).equals(find_returnRot(b));
    }
}

public class 子类实例并查集 {
//    @Test
//    public void test() {
        public static void main(String[] args) {


       int n= 3;

       String[] ss = {"student subClassOf person",
               "Tom instanceOf student",
               "Marry instanceOf person"
       };
       String t= "person";


        List<String> list = new ArrayList<>();
        List<String> res = new ArrayList<>();
        List<String[]> ned = new ArrayList<>();
        for (int i = 0; i < ss.length; i++) {
            if(ss[i].contains("subClassOf")){
                list.add(ss[i]);
            }else if(ss[i].contains("instanceOf")){
                String[] s = ss[i].split(" ");
                if(s[2].equals(t)){
                    res.add(s[0]);
                }else{
                    String[] a= new String[2];
                    a[0]=s[1];a[1]=s[0];
                    ned.add(a);
                }
            }
        }

        for (String[] s : ned) {
            for (int i = 0; i < list.size(); i++) {
                String s1 = list.get(i);
                if(s1.contains(s[0])){
                    s1.replace(s[0], s[1]);
                }
            }
        }

        String[] S = new String[list.size()];
        for (int i = 0; i < S.length; i++) {
            S[i] = list.get(i);
        }
        ConnectFind connectFind = new ConnectFind(S);

        for (int i = 0; i < list.size(); i++) {
            String[] s = list.get(i).split(" ");
            connectFind.connect(s[0],s[2]);
        }


        Set<String> set = new HashSet<>();
        for (int i = 0; i < list.size(); i++) {
            String[] s = list.get(i).split(" ");

            if(t.equals(connectFind.find_returnRot(s[0]))){
                set.add(s[0]);
            }
            if(t.equals(connectFind.find_returnRot(s[1]))){
                set.add(s[1]);
            }
        }

        List<String> RES = new ArrayList<>();
        for (int i = 0; i < res.size(); i++) {
            RES.add(res.get(i));
            System.out.println(res.get(i)+" ");
        }
        for(String s : set){
            RES.add(s);
            System.out.println(s+" ");
        }
    }

}
